1. Field of the Invention
The present invention relates to an automatic global routing device, in a CAD system which designs and develops a large-scale integrated circuit (LSI) and a logic circuit by means of a computer, for automatically placement and routing component cells on LSI chips or printed boards so as to minimize the entire size or minimize a routing length and a global routing method therefor.
2. Description of the Related Art
Automatic placement and routing processing of this kind for placement and routing integrated circuit chips by an automatic routing device using a CAD system is executed in four steps, floor plan processing, placement processing, global routing processing and detailed routing processing.
In the following, conventional automatic placement and routing methods will be described with reference to FIGS. 7 and 8. First, at the floor plan processing, one places macro cells on an integrated circuit to be processed, and determines a region in which basic cells are to be placed as shown in FIG. 8(A) (Step 701 of FIG. 7). This floor plan processing is conducted semi-automatically. Next, determination is made whether routing processing is possible for the integrated circuit subjected to the floor plan processing (Step 702). When the determination is made that routing is impossible, the routine returns to Step 701 to execute the floor plan processing over again.
When the determination is made at Step 702 that routing is possible, one places desired basic cells at the basic cell placement region as shown in FIG. 8(B) (Step 703). Then, determination is made whether routing processing is possible for the integrated circuit subjected to the basic cell placement processing (Step 704). When the determination is made that routing is impossible, the routine returns to Step 703 to conduct the placement processing over again. When the determination is still made at Step 704 that routing is impossible even after further trials of the placement processing a preset number of times, the routine returns to Step 701 to start over with the floor plan processing.
When the determination is made at Step 704 that routing is possible, one divides the integrated circuit chip to be processed into rectangles (global routing cells) and determines a routing route of each net on a divisional unit basis as shown in FIG. 8(C) (Step 705). xe2x80x9cNetxe2x80x9d here represents a route from an output terminal of an arbitrary gate circuit to an input terminal of other gate circuit. For each net, net information indicating which terminals are to be connected is defined. Global routing processing at Step 705 is conducted based only on a wire capacitance of a global routing cell boundary (degree of wire congestion) as will be described later. Next, determination is made whether routing processing is possible for the integrated circuit subjected to the global routing processing (Step 706). When the determination is made that routing is impossible, the routine returns to Step 705 to conduct the global routing processing over again. When the determination is still made at Step 706 that routing is impossible even after further trials of the global routing processing a preset number of times, the routine returns to Step 703 to conduct the placement processing over again. Furthermore, when the determination is still made at Step 706 that routing is impossible even after further trial of the placement processing a preset number of times, the routine returns to Step 701 to start over with the floor plan processing.
When the determination is made at Step 706 that routing is possible, one determines a detailed routing route within each global routing cell as shown in FIG. 8(D) (Step 707). Then, one determines if there is a shorted net or an unrouted net (Step 708). When there is a shorted net or an unrouted net, the routine returns to Step 707 to conduct the detailed routing processing over again. If a shorted net or an unrouted net is still detected at Step 708 even after further trials of the detailed routing processing preset times, the routine returns to Step 705 to conduct the global routing processing over again. Further, when a shorted place or a place yet to be wired is still detected at Step 708 even after further executions of the global routing processing preset times, the routine returns to Step 703 to start over with the placement processing. Further, if a shorted place or a place yet to be wired is still detected at Step 708 even after further executions of the placement processing preset times, the routine returns to Step 701 to start over with the floor plan processing. Then, when there remains neither a shorted place nor a place yet to be wired (yes at Step 708), the automatic placement and routing processing is completed.
Next, with reference to FIG. 9, detailed description will be made of the global routing processing (FIG. 7, Step 705) and the following routing possibility/impossibility determination processing (FIG. 7, Step 706) at the conventional automatic placement and routing processing. Conventional global routing processing of this kind is disclosed, for example, in Japanese Patent Laying-open (Kokai) No. Heisei 3-278446, entitled xe2x80x9cAutomatic Routing Method for Semiconductor Devicexe2x80x9d.
First, as shown in FIG. 10(A), divide a chip into rectangles (global routing cells) (Step 901). In FIG. 10(A), a black square represents a terminal, while a region denoted by slant lines represents a global route for the connection of terminals. xe2x80x9cGlobal routing cellxe2x80x9d is also called a unit routing region. In the figure, a boundary between adjacent global routing cells is called a xe2x80x9cglobal routing cell boundaryxe2x80x9d. More specifically, each global routing cell has four global routing boundaries in the upper, lower, right and left directions.
Next, calculate a wire capacitance which indicates how many wires can pass through each global routing cell boundary (Step 902). With reference to FIG. 11, a method of calculating a wire capacitance will be described. In FIG. 11, one specific global routing cell is denoted by solid lines and a routing track is denoted by a dotted line. Here, xe2x80x9crouting trackxe2x80x9d represents a passage on which routing can be made. xe2x80x9cWire capacitancexe2x80x9d is therefore equal to the number of routing tracks passing through a global routing cell boundary. In addition, a routing inhibited region is denoted as a block of slant lines. In practice, routing is made over a plurality of layers. In other words, routing tracks and routing inhibited regions exist individually on each layer in practice. In this example, description will be made of one-layer routing for the purpose of simplicity. In the example illustrated in FIG. 11, five routing tracks exist in the right-and-left direction and five routing tracks also exist in the up-and-down direction. In this case, if there exists no routing inhibited region within the global routing cell and on the global routing cell boundaries, a wire capacitance of each global routing cell boundary will be 5.
However, since a routing inhibited region exists in practice as illustrated in FIG. 11, a wire capacity of each global routing cell boundary will be 5 or less than 5 which is a value derived from the number of routing tacks. In the example shown in FIG. 11, the symbol xe2x80x9c∘xe2x80x9d on a global routing cell boundary denotes a passable track, and a wire capacity of the upper global routing cell boundary is 3, that of the lower global routing cell boundary is 4, that of the left-side global routing cell boundary is 5 and that of the right-side global routing cell boundary is 3. Here, according to the above literature, a wire capacity is obtained as the number of routing tracks allowing routing which is estimated based on a distribution of obstructions within the global routing cell (routing inhibited region). In the global routing processing, therefore, a routing route is selected such that a wire capacity will not exceed an estimated value at each global routing cell boundary.
Next, based on a wire capacity of a global routing cell boundary and already determined global routes, calculate a degree of congestion of wires which indicates how many wires can be actually passed through a global routing cell boundary (Step 903). With a global route set as shown in FIG. 10(A), a global routing cell boundary through which a wire passes is denoted by an arrow in FIG. 10(B) and a global routing cell through which a wire passes is denoted as a block of heavy solid lines. This calculation of a degree of wire congestion is made per one net yet to be wired, using the following expression:
[[degree of wire congestion]=[the number of passing global routes]xe2x88x92[wire capacity]. 
Therefore, the higher a value of the degree of wire congestion is, that is, the closer to zero the value is, the more wires are congest. Zero value of the degree of wires congestion indicates that no more routing is possible on the global routing cell boundary. With reference to FIGS. 12 and 13 in addition to FIG. 11, a method of calculating a degree of wire congestion will be described. FIG. 12 shows already determined global routes. In this example, two global routes pass through the upper global routing cell boundary, one passes through the lower global routing cell boundary, two pass through the left-side global routing cell boundary and three pass through the right-side global routing cell boundary. Calculation of a degree of wire congestion based on the wire capacities shown in FIG. 11 and the global routes shown in FIG. 12 results in that the degree of wire congestion on the upper global routing cell boundary will be xe2x88x921 (=2xe2x88x923) as shown in FIG. 13 because the number of passing global routes is two and the wire capacitance is 3. Similarly, the degree of wire congestion on the lower global routing cell boundary will be xe2x88x923 (=1xe2x88x924), that of the left-side global routing cell boundary will be xe2x88x923 (=2xe2x88x925)and that of the right-side global routing cell boundary will be 0 (=3xe2x88x923).
Next, based on the cost of distance, the cost of a degree of wire congestion on a global routing cell boundary, the cost of bend and other various kinds of costs, one determines a routing route minimizing these costs (Step 904). Then, Steps 903 and 904 will be repeated until there remains no more unrouted net (Step 905). In other words, determination of a route minimizing these costs is made through Steps 903, 904 and 905 taking wire capacitances into consideration until no unrouted net wired is left.
When no more nets remain to be wired (no at Step 905), determination is made whether there exists a global routing cell boundary at which the number of passing wires exceeds its wire capacitance (that is, a global routing cell boundary with a positive value of the degree of wire congestion) (Step 906). Here, when there exists a global routing cell boundary at which the number of passing wires exceeds its wire capacitance, one rips up a net which passes through the global routing cell boundary (Step 907) to return to Step 903. On the other hand, when there exists no global routing cell boundary at which the number of passing wires exceeds its wire capacitance, the global routing processing is completed.
The automatic placement and routing processing by a conventional automatic routing device, however, has the following drawback because global routing processing is conducted taking only a wire capacitance of a global routing cell boundary into consideration, that is, based only on a degree of wire congestion as mentioned above.
Consideration will be given of a global routing cell with three routing tracks existing in the right-and-left direction and three routing tracks also in the up-and-down direction as illustrated in FIG. 14(A). It is assumed that in this global routing cell, a region denoted by slant lines and including a point of intersection between the central routing track in the right-and-left direction and the central routing track in the up-and-down direction (hereinafter referred to as a central point of intersection) is a routing inhibited region. In such a case, wire capacitances of the respective global routing cell boundaries are all 3.
With this global routing cell, to pass three wires as a global route in the right-and-left direction as shown in FIG. 14(B) results in having such degrees of wire congestion on the global routing cell boundaries as shown in FIG. 14(C), none of which has a positive value (i.e., none of which has exceeded routing cell capacity). In other words, the number of nets passing through the global routing cell boundary does not exceed a wire capacitance. Determination is therefore made here that the routing in question is possible. However, since routing that passes through the central point of intersection is actually impossible because of the existence of the routing inhibited region, even if determination is made at the global routing processing that routing is possible, routing error will occur at the subsequent detailed routing processing as shown in FIG. 14(D). This is because two nets are shorted as illustrated in FIG. 14(D). As a result, the global routing processing or the preceding placement processing and floor plan processing must be conducted over again.
In brief, automatic routing and placement processing by a conventional automatic routing device has a disadvantage in taking much time because even when determination is made at global routing processing that routing is possible, it is highly probable that determination will be made at the detailed routing processing that such routing is impossible.
An object of the present invention is to provide an automatic routing device enabling reduction in time required for automatic placement and routing processing by lessening a probability that routing determined to be possible at global routing processing will be determined to be impossible at detailed routing processing.
According to the first aspect of the invention, automatic routing device for automatically conducting placement and routing of integrated circuits on an integrated circuit chip to be processed, comprises
first determination means for determining whether routing of a desired net is possible or not based on a wire capacitance at each global routing cell boundary formed by the division of the logic circuit chip into global routing cells, and
second determination means for determining whether routing of a desired net is possible or not based on a state of the use of a routing track grid in each global routing cell formed on the logic circuit chip.
In the preferred construction, the second determination means determines whether routing of the desired net is possible or not based on, out of grids as points of intersection between the routing tracks, the number of grids usable for routing.
In the preferred construction, the second determination means comprises number of usable grids calculating means for calculating, out of grids as points of intersection between the routing tracks, the number of grids usable for routing, number of grids to be used calculating means for calculating, based on a passing route of wires passing in the global routing cell, the number of grids to be used by the wires out of the grids, and routing possibility/impossibility determining means for determining whether routing of the desired net is possible or not based on a ratio of the number of grids usable for routing to the number of grids to be used by the wires.
In the preferred construction, the second determination means comprises number of usable grids calculating means for calculating, out of grids as points of intersection between the routing tracks, the number of grids usable for routing, number of grids to be used calculating means for calculating, based on a passing route of wires passing in the global routing cell, the number of grids to be used by the wires out of the grids, and determination means for comparing the number of grids usable for routing and the number of grids to be used by wires to determine that the routing is impossible when the number of grids to be used by wires is larger.
According to the second aspect of the invention, an automatic routing device for automatically conducting placement and routing of integrated circuits on an integrated circuit chip to be processed, comprises
floor plan determining means for conducting floor plan processing,
basic cell placement means for conducting basic cell placement processing,
global routing route determining means for conducting global routing processing, and
detailed routing route determining means for conducting detailed routing processing,
the global routing route determining means comprising
first determination means for determining whether routing of a desired net is possible or not based on a wire capacitance at each global routing cell boundary formed by the division of the logic circuit chip into global routing cells, and
second determination means for determining whether routing of a desired net is possible or not based on a state of the use of a routing grid track in each global routing cell formed on the logic circuit chip.
In the preferred construction, the second determination means determines whether routing of the desired net is possible or not based on, out of grids as points of intersection between the routing tracks, the number of grids usable for routing.
In the preferred construction, the second determination means comprises number of usable grids calculating means for calculating, out of grids as points of intersection between the routing tracks, the number of grids usable for routing, number of grids to be used calculating means for calculating, based on a passing route of wires passing in the global routing cell, the number of grids to be used by the wires out of the grids, and routing possibility/impossibility determining means for determining whether routing of the desired net is possible or not based on a ratio of the number of grids usable for routing to the number of grids to be used by the wires.
In another preferred construction, the second determination means comprises number of usable grids calculating means for calculating, out of grids as points of intersection between the routing tracks, the number of grids usable for routing, number of grids to be used calculating means for calculating, based on a passing route of wires passing in the global routing cell, the number of grids to be used by the wires out of the grids, and determination means for comparing the number of grids usable for routing and the number of grids to be used by wires to determine that the routing is impossible when the number of grids to be used by wires is larger.
According to the third aspect of the invention, an automatic routing method of automatically conducting placement and routing of integrated circuits on an integrated circuit chip to be processed, comprising the steps of:
conducting floor plan processing,
conducting basic cell placement processing,
conducting global routing processing, and
conducting detailed routing processing,
the global routing processing step comprising the steps of
dividing the logic circuit chip into global routing cells,
calculating a wire capacitance of each global routing cell boundary formed at the division step,
out of grids as points of intersection between routing tracks in each global routing cell formed at the division step, calculating the number of grids usable for routing,
based on a passing route of wires passing in the global routing cell, calculating the number of grids to be used by the wires out of the grids,
comparing the number of grids usable for routing calculated at the number of usable grids calculating step and the number of grids to be used by the wires calculated at the number of grids to be used calculating step,
determining a routing route of every net such that at least the cost of the degree of wire congestion calculated at the wire capacitance calculating step and the cost of grid use rate for routing calculated at the number of usable grids calculating step are minimum,
determining whether routing according to a routing route determined at the routing route determining step is possible or not based on the degree of wire congestion calculated at the wire capacitance calculating step, and
determining whether routing according to a routing route determined at the routing route determination step is possible or not based on a comparison result obtained at the number of grids comparing step.
In the preferred construction, the step of determining whether routing is possible or not based on a wire capacitance comprises the steps of:
determining whether there exists the global routing cell boundary through which a larger number of wires pass than the wire capacitance calculated at the wire capacitance calculating step, and when determination is made at the determination step that there exists the global routing cell boundary through which a larger number of wires pass than the wire capacitance, ripping up a net passing through the global routing cell boundary to return the processing to the route determination step.
In the preferred construction, the step of determining whether routing is possible or not based on a ratio of the number of grids usable for routing to the number of grids to be used for the wires comprises the steps of:
determining whether there exists the global routing cell in which the number of grids to be used for the wires is larger than the number of grids usable for routing, and
when determination is made at the determination step that there exists the global routing cell in which the number of grids to be used for the wires is larger than the number of grids usable for routing, ripping up a net passing through the global routing cell to return the processing to the route determination step.
In another preferred construction, the step of determining whether routing is possible or not based on a wire capacitance comprises the steps of:
determining whether there exists the global routing cell boundary through which a larger number of wires pass than the wire capacitance calculated at the wire capacitance calculating step, and
when determination is made at the determination step that there exists the global routing cell boundary through which a larger number of wires pass than the wire capacitance, ripping up a net passing through the global routing cell boundary to return the processing to the route determination step, and
the step of determining whether routing is possible or not based on a ratio of the number of grids usable for routing to the number of grids to be used for the wires comprises the steps of:
determining whether there exists the global routing cell in which the number of grids to be used for the wires is larger than the number of grids usable for routing, and
when determination is made at the determination step that there exists the global routing cell in which the number of grids to be used for the wires is larger than the number of grids usable for routing, ripping up a net passing through the global routing cell to return the processing to the route determination step.
According to another aspect of the invention, a computer readable memory storing a control program for controlling an automatic routing device which automatically places and wires integrated circuits on an integrated circuit chip to be processed,
the control program comprising the steps of:
conducting floor plan processing,
conducting basic cell placement processing,
conducting global routing processing, and
conducting detailed routing processing,
the global routing processing step comprising the steps of
dividing the logic circuit chip into global routing cells,
calculating a wire capacitance of each global routing cell boundary formed at the division step,
out of grids as points of intersection between routing tracks in each global routing cell formed at the division step, calculating the number of grids usable for routing,
based on a passing route of wires passing in the global routing cell, calculating the number of grids to be used by the wires out of the grids,
comparing the number of grids usable for routing calculated at the number of usable grids calculating step and the number of grids to be used by the wires calculated at the number of grids to be used calculating step,
determining a routing route of every net such that at least the cost of the wire capacitance calculated at the wire capacitance calculating step and the cost of the number of grids usable for routing calculated at the number of usable grids calculating step are minimum,
determining whether routing according to a routing route determined at the routing route determining step is possible or not based on the wire capacitance calculated at the wire capacitance calculating step, and
determining whether routing according to a routing route determined at the routing route determination step is possible or not based on a comparison result obtained at the number of grids comparing step.
Other objects, features and advantages of the present invention will become clear from the detailed description given herebelow.